package sort

func MergeSort1(arr []int){
	if arr == nil || len(arr) < 2 {return}
	process(arr, 0, len(arr)-1)
}

func MergeSort2(arr []int) {
	if arr == nil || len(arr) < 2 {return}
	process2(arr, 0, len(arr)-1)
}

func process2(arr []int, l, r int) {
	step := 1
	for step <= r {
		curL := 0
		for curL < r {
			M := curL+step-1
			if M>=r{
				break
			}
			R := M+step
			if R > r {
				R = r
			}
			Partition(arr, curL, R, M)
			curL = R + 1
		}
		step *= 2
	}

}

func process(arr []int, l, r int){
	if r == l {return }
	middle := l + (r-l) >> 1
	process(arr, l, middle)
	process(arr, middle+1, r)
	Partition(arr, l, r, middle)
}

func Partition(arr []int, l, r, middle int) {
	ans := make([]int, r-l+1)
	p1, p2 := l, middle+1
	index := 0
	for p1<=middle && p2 <= r {
		if arr[p1] <= arr[p2] {
			ans[index] = arr[p1]
			index++
			p1++
		} else {
			ans[index] = arr[p2]
			index++
			p2++
		}
	}
	for p1 <= middle {
		ans[index] = arr[p1]
		index ++
		p1++
	}
	for p2 <= r {
		ans[index] = arr[p2]
		index ++
		p2++
	}
	for i:=0; i<len(ans); i++ {
		arr[l] = ans[i]
		l++
	}
}